import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Test
{
    public static int[] missingTwo(int[] nums)
    {
        int n=nums.length;
        int []ans=new int[2];
        int x=0,x1=0,x2=0;
        int move=0;
        //
        for (int i = 1; i <=n+2 ; i++) x^=i;
        for (int num : nums) x ^= num;
        x&=(-x);//提取右边第一个1
        for (int i = 0; true; i++)
        {
            if((x>>i&1)==1)
            {
                move=i;break;
            }
        }
        for (int i = 1; i <= n+2; i++)
        {
            if((i>>move&1)==1) x1^=i;
            else x2^=i;
        }
        for (int num : nums) {
            if ((num >> move & 1) == 1) x1 ^= num;
            else x2 ^= num;
        }
        ans[0]=x1;
        ans[1]=x2;
        return ans;
    }
    public static String modifyString(String ss) {
        int n=ss.length();
        char[]s=ss.toCharArray();
        for (int i = 0; i < n; i++) {
            if(s[i]=='?'){
                for (char j = 'a'; j <= 'z'; j++) {
                    if((i==0||s[i-1]!=j)&&(i==n-1||s[i+1]!=j)) s[i]=j;
                }
            }
        }
        ss= String.valueOf(s);
        return ss;
    }
    public static int findPoisonedDuration(int[] timeSeries, int duration){
        int ret = 0,n = timeSeries.length;
        for (int i = 0; i < n; i++) {
            ret += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        }
        ret += duration;
        return ret;
    }
    public static String convert(String s, int numRows) {
        StringBuilder ret = new StringBuilder();
        if(numRows==1)  return s;
        int n = s.length(), r = numRows, t = 2 * r - 2 , c = (r - 1)* (n+t-1) / t;
        char[][] tmp = new char[r][c];
        int x=0,y=0;
        for (int i = 0; i < n; i++) {
            if(i % t< r - 1){
                tmp[x][y]=s.charAt(i);
                x++;
            }else{
                tmp[x][y]=s.charAt(i);
                x--;
                y++;
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(tmp[i][j]!=0){
                    ret.append(tmp[i][j]);
                }
            }
        }
        return ret.toString();
    }

    public static String countAndSay(int n){
        String ret="1";
        for(int i = 1; i < n; i++){
            StringBuilder tmp = new StringBuilder();
            int len=ret.length();
            for(int left = 0,right = 0; right < len; ){
                while(right < len && ret.charAt(left) == ret.charAt(right)) right++;
                tmp.append(Integer.toString(right - left));
                tmp.append(ret.charAt(left));
                left = right;
            }
            ret = tmp.toString();
        }
        return ret;
    }

    public static int minNumberOfFrogs(String croakOfFrogs) {
         int []hash=new int[26];
         char[] s=croakOfFrogs.toCharArray();
         int n=s.length,ret=0;
         for (int i = 0; i < n; i++) {
             if(s[i] == 'c') {
                 if(hash['k'-'a'] != 0) hash['k'-'a']--;
                 hash['c'-'a']++;
             }
             if(s[i] == 'r'){
                 if(hash['c'-'a'] != 0) {
                     hash['c'-'a']--;
                     hash['r'-'a']++;
                 }else{
                     return -1;
                 }
             }
             if(s[i] == 'o'){
                 if(hash['r'-'a'] != 0) {
                     hash['r'-'a']--;
                     hash['o'-'a']++;
                 }else{
                     return -1;
                 }
             }
             if(s[i] == 'a'){
                 if(hash['o'-'a'] != 0) {
                     hash['o'-'a']--;
                     hash['a'-'a']++;
                 }else{
                     return -1;
                 }
             }
             if(s[i] == 'k'){
                 if(hash['a'-'a'] != 0) {
                     hash['a'-'a']--;
                     hash['k'-'a']++;
                 }else{
                     return -1;
                 }
             }
         }
        for(int i = 0; i <26; i++){
            if(i != 'k'-'a' && hash[i] != 0) return -1;
        }
        ret=hash['k'-'a'];
        return ret;

    }
    public static int minNumberOfFrogs1(String c){
        String t="croak";
        char[] croakOfFrogs=c.toCharArray();
        int n=t.length(),ret=0;
        int []hash=new int[n];
        Map<Character,Integer> index=new HashMap<>();
        for (int i = 0; i < n; i++) {
            index.put(t.charAt(i),i);
        }
        for(char ch: croakOfFrogs) {
            if (ch == t.charAt(0)) {
                if (hash[n - 1] != 0) {
                    hash[0]++;
                }
            } else {
                int i = index.get(ch);
                if (hash[i - 1] == 0) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }
        for (int i = 0; i < n-1; i++) {
            if(hash[i] !=0 ) return -1;
        }
        return ret;
    }
    public static void swap(int [] nums,int e1,int e2){
        int tmp=nums[e1];
        nums[e1]=nums[e2];
        nums[e2]=tmp;
    }

    public  static void sortColors(int[] nums){
        int n=nums.length;
        int left=-1,right=n;
        for (int i = 0; i < right; ) {
            if( nums[i] == 0) swap(nums,++left,i++);
            else if( nums[i] == 1) i++;
            else swap(nums,--right,i);
        }
    }
    public static void sortArray(int []nums){
        quickSort(nums,0, nums.length - 1);
    }

    public static  void quickSort(int[]  nums,int l, int r){
        if(l>=r) return;
        Random random = new Random();
        int randNum = random.nextInt(r - l + 1) + l;
        int left = l - 1, right = r + 1;
        int key = nums[randNum];
        for (int i = l; i < right; ) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if (nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        quickSort(nums, l,left);
        quickSort(nums, right,r);
    }
    public static void adjustDown(int []nums,int parent,int n){
        int child = 2 * parent + 1;
        while(child < n){
            if(child+1 < n && nums[child+1] > nums[child]) child++;
            if(nums[parent] < nums[child])
            {
                swap(nums, parent, child);
                parent = child;
                child = child * 2 + 1;
            }else
                break;
        }
    }
    public static void pop(int[] nums,int n){
        swap(nums,0,n-1);
        adjustDown(nums,0,n-1);
    }

    public static int findKthLargest(int[] nums, int k) {
        //建立大堆 第k大就弹k次
        int n = nums.length;
        for(int i = (n-1-1)/2; i >=0; i--){
            adjustDown(nums,i,n);
        }
        while(k > 1){
            pop(nums,n);
            n--;
            k--;
        }
        return nums[0];
    }

    public static int qsort(int []nums, int l, int r, int k)
    {
        if(l == r) return nums[l];

        Random random = new Random();
        int randNum = random.nextInt(r - l + 1) + l;
        int key = nums[randNum];

        int left = l - 1, right = r + 1;
        for (int i = l; i < right; )
        {
            if(nums[i] < key) swap(nums,++left,i++);
            else if (nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        int b=right - l - 1, c =r -right +1;
        if(k <= c) return qsort(nums, right, r, k);
        else if(k <= b+c) return key;
        else  return qsort(nums, left, l,k-b-c);
    }

    public static int findKthLargest1(int[] nums, int k){
        return qsort(nums,0,nums.length-1,k);
    }
    public static void qsort1(int [] arr, int l, int r, int k)
    {
         int left = l - 1, right = r + 1;
         int key = arr[new Random().nextInt(r - l +1) + l];

        for (int i = l; i < right; )
        {
            if(arr[i] < key) swap(arr, ++left, i++);
            else if(arr[i] == key) i++;
            else swap(arr, --right, i);
        }

        int a = left- l + 1,b = right - left - 1;
        if(a > k) qsort1(arr, l, left, k);
        else if(a + b >= k) return ;
        else  qsort1(arr, right, r,k - a - b);
    }
    public static int[] getLeastNumbers(int[] arr, int k){
         qsort1(arr,0,arr.length - 1,k);
         int [] ret= new int[k];
        System.arraycopy(arr, 0, ret, 0, k);
         return ret;
    }
    
    public static void mergeSort(int[]arr, int l , int r){
        int mid=l+r >> 1;
        if(l==r) return ;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        int [] tmp =new int[r - l +1];
        int i = l , j = mid +1 ,k = 0, len=r - l +1;
        while(i<= mid && j <= r)
        {
          tmp[k++] = arr[i] < arr[j] ? arr[i++] :arr[j++];
        }
        while(i <= mid){
            tmp[k++] = arr[i++];
        }
        while(j <= r){
            tmp[k++] = arr[j++];
        }
        System.arraycopy(tmp,0,arr,l,len);
//        for (int m = 0; m < len; m++) {
//            arr[l++] = tmp[m];
//        }
    }

    public static void main(String[] args) {
        int []arr = {3,2,1,5,6,4};
        mergeSort(arr, 0, arr.length -1);
        System.out.println(Arrays.toString(arr));
    }

    public static void main9(String[] args) {
         int []arr = {3,2,1,5,6,4};
        System.out.println(Arrays.toString(getLeastNumbers(arr, 3)));
    }


    public static void main8(String[] args) {
        int[] arr = {3,2,1,5,6,4};
        System.out.println(findKthLargest1(arr, 4));
    }

    public static void main7(String[] args) {
        int []arr = {3,2,1,5,6,4};
        System.out.println(findKthLargest(arr, 2));
    }

    public static void main6(String[] args) {
        int [] nums={5,2,3,1};
        sortArray(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void main5(String[] args) {
        int []nums={2,0,2,1,1,0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }


    public static void main4(String[] args) {
        int ret=minNumberOfFrogs("crcoakroak");
        System.out.println(ret);
    }

    public static void main3(String[] args) {
        String ret=countAndSay(5);
        System.out.println(ret);
    }

    public static void main2(String[] args) {
        String s = "ABC";
        String ret = convert(s,2);
        System.out.println(ret);
    }

    public static void main1(String[] args)
    {
        int []arr={1, 2, 3, 4, 6, 7, 9, 10};
        int[]ret=missingTwo(arr);
        System.out.println(Arrays.toString(ret));
    }
}
